/*
1443.收集树上所有苹果的最少时间
https://leetcode.cn/problems/minimum-time-to-collect-all-apples-in-a-tree/description/
中等 2024/11/10
*/

class Solution {
public:
unordered_map<int,vector<int>>mp;
int dfs(int root,vector<bool>& hasApple,vector<int>& visit)
{
    visit[root]=true;//防止重复遍历
    int ans=0;//统计个数
    bool flag=false;
    for(auto i : mp[root])
    {
        if(visit[i]) continue;
        ans+=dfs(i,hasApple,visit);
        if(hasApple[i]) 
            ans+=2;
    }
    if(hasApple[root]) flag=true;//当前节点为苹果,就已经+2步数了,防止多次+2
    if (root == 0 || flag) return ans; //根节点不增加额外步数
    return ans > 0 ? ans + 2 : 0; // 只有当子树中有苹果时才增加步数
}
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
    vector<int>visit(n,false);
    for(int i=0;i<edges.size();i++)
    {
        mp[edges[i][0]].push_back(edges[i][1]);//无向图
        mp[edges[i][1]].push_back(edges[i][0]);
    }
        return dfs(0,hasApple,visit);
    }
};